package main

import "fmt"

/*
树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:
     3
    / \
   4   5
  / \
 1   2

给定的树 B：
   4
  /
 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func isSubStructure(A *TreeNode, B *TreeNode) bool {

	var recur func(*TreeNode, *TreeNode) bool
	recur = func(A *TreeNode, B *TreeNode) bool {
		if B == nil {
			return true
		}
		if A == nil || A.Val != B.Val {
			return false
		}
		return recur(A.Left, B.Left) && recur(A.Right, B.Right)
	}
	return (A != nil && B != nil) && (recur(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B))
}

func main() {
	A := &TreeNode{Val: 1}
	A.Left = &TreeNode{Val: 2}
	A.Right = &TreeNode{Val: 3}
	A.Left.Left = &TreeNode{Val: 4}
	A.Left.Right = &TreeNode{Val: 5}
	A.Right.Left = &TreeNode{Val: 6}

	B := &TreeNode{
		Val:  2,
		Left: &TreeNode{Val: 4},
	}

	aa := isSubStructure(A, B)
	fmt.Println(aa)
}
